/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return;
        
        // 快慢指针找中点
        ListNode* fast = head, *slow = head;
        while(fast->next != nullptr && fast->next->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* mid = slow->next;  // 中点
        slow->next = nullptr;   // 断开链表

        // 反转后半部分链表
        ListNode* pre = nullptr;
        while(mid != nullptr){
            ListNode* next = mid->next;
            mid->next = pre;
            pre = mid;
            mid = next;
        }
        // 逐结点合并两两链表
        fast = head;
        ListNode* cur1 = head, *cur2 = pre;
        while(fast != nullptr && pre != nullptr){
            cur1 = fast->next;
            cur2 = pre->next;

            fast->next = pre;
            fast = cur1;
            
            pre->next = fast;
            pre = cur2;
        } 
    }
};